package org.lyc.lanqiao;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * 图生成器
 *
 * @author Liu Yicong
 * @date 2024/3/11
 */
public class GenerateRandomGraph {

	public static void main(String[] args) {
		generateRandomGraph(8);
		generateRandomGraph(10);
		generateRandomGraph(15);
	}

	private static void generateRandomGraph(int n) {
		System.out.println(n);

		// 构建边的数量等于节点数量的图
		int edgeCount = n;
		Random random = new Random();
		Set<String> edgesSet = new HashSet<>();

		// 生成边
		while (edgesSet.size() < edgeCount) {
			int u = random.nextInt(n) + 1;
			int v = random.nextInt(n) + 1;

			if (u != v) {
				edgesSet.add(Math.min(u, v) + " " + Math.max(u, v));
			}
		}

		// 输出边
		for (String edge : edgesSet) {
			System.out.println(edge);
		}

		System.out.println();
	}
}
